import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;

public class Fibonacci {
    private static Integer[] fibonacci = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987};
    private static final int PRECALCULATED_NUMBERS_SIZE = fibonacci.length;
    private static final List<Integer> fibonacciNumbers = new ArrayList<Integer>(Arrays.asList(fibonacci));

    public static void main(String[] args) {
        final int n = 40;
        long start = System.nanoTime();
        int fib = calculateFibonacci(n);
        long end = System.nanoTime();
        System.out.println("Fibonacci[" + n + "] = " + fib + "  generated in " + TimeUnit.NANOSECONDS.toMillis((end - start)) + "ms.");

        start = System.nanoTime();
        fib = recursiveFib(n);
        end = System.nanoTime();
        System.out.println("Fib recur[" + n + "] = " + fib + "  generated in " + TimeUnit.NANOSECONDS.toMillis((end - start)) + "ms.");
    }

    private static int calculateFibonacci(int n) {
        if (n < 0) throw new IllegalArgumentException("The Fibonacci number's index must be non-negative");
        final int generatedFibsAmount = fibonacciNumbers.size();
        if (n < generatedFibsAmount) return fibonacciNumbers.get(n);
        int prev = fibonacciNumbers.get(generatedFibsAmount - 2);
        int cur = fibonacciNumbers.get(generatedFibsAmount - 1);
        for (int i = generatedFibsAmount; i <= n; i++) {
            int newNumber = cur + prev;
            fibonacciNumbers.add(newNumber);
            prev = cur;
            cur = newNumber;
        }
        return cur;
    }

    private static int recursiveFib(int n) {
        if (n < 0) throw new IllegalArgumentException("The input parameter (" + n + ") must be non-negative");
        if (n == 0) return 0;
        if (n == 1) return 1;
        return recursiveFib(n - 1) + recursiveFib(n - 2);
    }
}
